package com.atwulidun.sort;

import java.util.Arrays;

public class RedixSort {
    public static void main(String[] args) {
        int[] arr = {-1, -33, 5, 3, 44, 3, 26, 1, 6, 7, -21};
        redixSort(arr);
        System.out.println("排序完后为：");
        System.out.println(Arrays.toString(arr));
    }

    //    public static void redixSort(int[] arr) {
//        // 一、处理arr中有负数的情况：
//        // 1.先找到最小的负数
//        int minNegative = 0;
//        for (int j : arr) {
//            if (j < 0) {
//                if (j < minNegative) {
//                    minNegative = j;
//                }
//            }
//        }
//        // 2.把数组中所有的数都减去minNegative，这样数组中所有数都变成了非负数
//        // 特别特别注意：所以增强for循环只适合用于数据的读取，要想改变数组中的元素的值，还是通过索引使用 arr[index] 这样的方法赋值
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] -= minNegative;
//        }
//
//        // 二、获取非负数数组arr中最大数的位数，并以此确定进行基数排序的轮数
//        int max = -1;
//        for (int i : arr) {
//            if (i > max) {
//                max = i;
//            }
//        }
//        int times = (max + "").length();
//
//        // 三、创建bucket和bucketElementCount
//        // 1.创建一个二维数组bucket，行表示每个桶，每个桶的大小为arr的大小，以防所有arr的元素都落在一个桶中
//        int[][] bucket = new int[10][arr.length];
//        // 2.创建一个一位数组bucketElementCount来保存每一轮基数排序每个桶中元素的个数
//        int[] bucketElementCount = new int[10];
//
//        // 四、开始进行基数排序
//        // 1.第一层循环控制排序的轮数，b用来求取每一轮排序的基数
//        for (int i = 0, b = 1; i < times; i++, b *= 10) {
//            // 2.第二层循环获取该轮数组中每个元素对应的基数，并按照基数把每个元素放到相应桶的相应位置中
//            for (int j = 0; j < arr.length; j++) {
//                // 求出当前元素要放在第几个桶
//                int bucketNum = arr[j] / b % 10;// 这里之前出错了：把arr[j]写成j了，粗心！！！！！！！！！！！！
//                bucket[bucketNum][bucketElementCount[bucketNum]] = arr[j];// 假如之前该桶已经有了2个元素，那么第3个元素的下标就是2
//                bucketElementCount[bucketNum]++;// 该桶的元素个数要加1
//            }
//            // 3.对每个桶中的元素按桶的下标从小到大、在桶中的排列从前到后的顺序赋值到arr中
//            int index = 0;// 定义一个index指向arr的每一个元素
//            // a.外层循环对每个桶按下标从小到大的顺序进行遍历
//            for (int m = 0; m < 10; m++) {
//                // 如果某个桶是空的，则直接跳过即可
//                if (bucketElementCount[m] != 0) {
//                    // b.内层循环将不为空的桶中的元素依次赋值给arr(对当前桶中的元素进行遍历)
//                    for (int n = 0; n < bucketElementCount[m]; n++) {
//                        arr[index++] = bucket[m][n];
//                    }
//                    // c.特别重要的一点：必须对当前桶的数量进行一个清零，以不影响下一轮排序！！！！！！
//                    bucketElementCount[m] = 0;
//                }
//            }
//        }
//        // 五、将arr还原，数组中的元素全部加上minNegative
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] += minNegative;
//        }
//    }
    private static void redixSort(int[] arr) {
        int minNegative = 0;
        for (int i : arr) {
            if (i < 0 && i < minNegative) {
                minNegative = i;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] -= minNegative;
        }
        int maxPositive = -1;
        for (int i : arr) {
            if (i > maxPositive) {
                maxPositive = i;
            }
        }
        int times = (maxPositive + "").length();
        int[][] buckets = new int[10][arr.length];
        int[] bucketElementCount = new int[10];
        for (int m = 0, b = 1; m < times; m++, b *= 10) {
            for (int i = 0; i < arr.length; i++) {
                int bucketNum = arr[i] / b % 10;
                buckets[bucketNum][bucketElementCount[bucketNum]] = arr[i];
                bucketElementCount[bucketNum]++;
            }
            int index = 0;
            for (int i = 0; i < 10; i++) {
                if (bucketElementCount[i] != 0) {
                    for (int j = 0; j < bucketElementCount[i]; j++) {
                        arr[index++] = buckets[i][j];
                    }
                    bucketElementCount[i] = 0;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] += minNegative;
        }
    }
}
